home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group99a.txt / 000191_icon-group-sender _Thu Sep 9 12:45:07 1999.msg < prev    next >
Internet Message Format  |  2000-09-20  |  5KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id MAA23587
  4.     for icon-group-addresses; Thu, 9 Sep 1999 12:43:22 -0700 (MST)
  5. Message-Id: <199909091943.MAA23587@baskerville.CS.Arizona.EDU>
  6. From: "Frank Lhota" <lhotaf@lexma.meitech.com>
  7. To: <icon-group@optima.CS.Arizona.EDU>
  8. Subject: Could we tend the result of memb?
  9. Date: Thu, 9 Sep 1999 13:46:07 -0400
  10. X-Priority: 3
  11. X-MSMail-Priority: Normal
  12. X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
  13. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  14. Status: RO
  15.  
  16. This message deals with the implementation of Icon, and assumes familiarity
  17. with the current implementation.
  18.  
  19. Icon implements sets and tables using a hash chain system. The structures
  20. for sets and tables are similar enough that they share a fair number of
  21. common utilities. One of the most commonly used utilities for set and table
  22. work is memb. The memb function determines whether a given item is a member
  23. of a set or table. This function has the following prototype:
  24.  
  25.     union block **memb  (union block *pb,dptr x,uword hn, int *res);
  26.  
  27. The pb parameter is a pointer to either a set or table block. The x
  28. parameter points to the descriptor of the value that memb will search for,
  29. and hn is the hash value for *x. After calling memb, *res receives whether
  30. *x cam be found in the set / table *pb (*res = 1 if the search succeeded, 0
  31. otherwise). The result of memb is a pointer to a block pointer member within
  32. some block that is part of the set / table representation. Assume we perform
  33.  
  34.     int res;
  35.     union block **slot;
  36.  
  37.     slot = memb(pb,x,hn,&res);
  38.  
  39. If *x was found in *pb (res == 1), *slot points to the set / table element
  40. in *pd for *x. If *x was not found in *pb (res == 0), *slot is the location
  41. that should receive the address of a newly created element for *x.
  42.  
  43. The handy, dandy memb function is useful for searching, modifying, adding
  44. and deleting the elements of a set or table. There is one problem, however,
  45. with memb: the result of memb cannot be tended. If a new block is allocated,
  46. the existing blocks may get moved around, and a stored memb result will be
  47. invalidated. Moreover, searches take a long time, so you really do not want
  48. to repeat a search unless absolutely necessary. To avoid invalidating the
  49. result of memb, several functions will perform an allocation before calling
  50. memb, even if we need to see the results of memb to determine if the
  51. allocation was actually needed. For example, the pseudo-code for inserting a
  52. value X into a set S is basically this.
  53.  
  54.     Allocate a new set element block;
  55.     Call memb to see if X is in S;
  56.     If ( X is not in S ) {
  57.         Fill in new set element block with data for X;
  58.         Link new set element block into S using result of memb;
  59.         }
  60.     else
  61.         Deallocate new set element block;    /* it was not really needed */
  62.  
  63. This approach is complicated, error prone and inefficient. If there was only
  64. some way to tend the result of memb, we could do the following more natural
  65. and efficient algorithm:
  66.  
  67.     Call memb to see if X is in S;
  68.     If ( X is not in S ) {
  69.         Allocate a new set element block;
  70.         Fill in new set element block with data for X;
  71.         Link new set element block into S using result of memb;
  72.         }
  73.  
  74. There is no known method for tending a value of type (union block **), since
  75. one cannot reliably find the start of the block that this value points into.
  76. Basically, memb is returning the address of a member in some block. Could
  77. memb return this information in another form that can be tended?
  78.  
  79. One possibility that comes to mind is that memb can return its result in a
  80. tended variable of type struct descrip. Remember, the result is always an
  81. address of a member of some block. We can store the start of this block in
  82. the BlkLoc part of the descriptor. The offset from the start of the block to
  83. the particular member can be stored in the Offset portion of the dword
  84. member of the descriptor. The resulting descriptor is in a form quite
  85. similar to descriptors that are currently tended. Consider an alternative
  86. form of memb:
  87.  
  88.     int memb  (union block *pb,dptr x,uword hn, dptr slot);
  89.  
  90. In this new version, the function return value indicates whether the search
  91. was successful (1 if search succeeded, 0 if failed). The slot parameter is
  92. the address of a tended descriptor. Upon return, we have:
  93.  
  94.     slot.dword = (F_Nqual | F_Ptr) | ( offset in words to the member )
  95.     BlkLoc(*s) = (Start of the block)
  96.  
  97. If we do this, should also add a macro that will turn such a descriptor into
  98. a (union block **) value.
  99.  
  100. Before I start working on this, I pose this question: does anyone know of a
  101. reason why this wouldn't work, or wouldn't be desirable?
  102.  
  103.